//给你一个字符串 s，找到 s 中最长的回文子串。
//
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
//
//
// Related Topics 字符串 动态规划 👍 6487 👎 0

// leetcode submit region begin(Prohibit modification and deletion)
package main

func longestPalindrome(s string) string {
	m := [][]bool{}
	n := len(s)
	for i := 0; i < n; i++ {
		m = append(m, make([]bool, n))
	}
	var o string

	for i := 0; i < n; i++ {
		m[i][i] = true
		o = s[i : i+1]
	}

	for i := 0; i < n-1; i++ {
		if s[i] == s[i+1] {
			m[i][i+1] = true
			o = s[i : i+2]
		}
	}

	for l := 3; l <= n; l++ { //这里犯过错，应该是<=
		for i := 0; i < n-l+1; i++ { //这里犯过错 i<n-l+1 注意+1
			if s[i] == s[i+l-1] && m[i+1][i+l-2] {
				m[i][i+l-1] = true
				o = s[i : i+l]
			}
		}
	}

	return o
}

//leetcode submit region end(Prohibit modification and deletion)
